/***************************************************
 * @Author: OBKoro1
 * @Create: 2021-02-21
 * @LastEditors: OBKoro1
 * @LastEditTime: 2021-02-21
 * @FilePath: \leetcode-exercise\37-解数独\sloveSudoku.c
 ****************************************************/

#define S 3       // 3x3 宫
#define N (S * S) // 9x9 数独
// 使用三个HASH数组(行、列、宫)来标识数字是否出现过
char rowUsed[N][N] = {0};
char colUsed[N][N] = {0};
char boxUsed[N][N] = {0};

inline bool couldFillIn(int d, int row, int col)
{
    int idx = (row / S) * S + col / S;
    return (rowUsed[row][d] + colUsed[col][d] + boxUsed[idx][d]) == 0;
}

inline void initNumber(void)
{
    memset(rowUsed, 0, sizeof(rowUsed));
    memset(colUsed, 0, sizeof(colUsed));
    memset(boxUsed, 0, sizeof(boxUsed));
}

inline void addNumber(int d, int row, int col)
{
    int idx = (row / S) * S + col / S;
    rowUsed[row][d]++; // = 1
    colUsed[col][d]++; // = 1;
    boxUsed[idx][d]++; // = 1;
}

inline void removeNumber(int d, int row, int col)
{
    int idx = (row / S) * S + col / S;
    rowUsed[row][d]--; // =0;
    colUsed[col][d]--; // =0;
    boxUsed[idx][d]--; // =0;
}

bool backtrackSudoku(char **board, int row, int col)
{
    // 3.边界条件
    if (col == N)
    {
        col = 0;
        row += 1;
        if (row == N)
        {
            return true; // 已经到最后一格，问题解决
        }
    }
    // 4.填入数字
    if (board[row][col] == '.')
    {
        for (int d = 1; d <= N; d++)
        { // 数字d从1到9进行循环判断/填入
            if (couldFillIn(d - 1, row, col))
            {
                board[row][col] = d + '0'; //填入数字d
                addNumber(d - 1, row, col);
                // 递归进行下一列(通过 3.边界条件 会自动换行)
                if (backtrackSudoku(board, row, col + 1))
                {
                    return true;
                }
                else
                {
                    // 5.回退措施, 让上一层能够回退回去填写下一个数
                    board[row][col] = '.';         // 将刚填的board[row][col]清空
                    removeNumber(d - 1, row, col); // 将三个数组恢复原值
                }
            }
        }
    }
    else
    {
        return backtrackSudoku(board, row, col + 1);
    }
    return false;
}

void solveSudoku(char **board, int boardSize, int *boardColSize)
{
    // 1.初始化
    initNumber();
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if ((board[i][j] != '.'))
            {
                int d = board[i][j] - '1';
                addNumber(d, i, j);
            }
        }
    }
    // 2.调用回溯函数
    backtrackSudoku(board, 0, 0);
}
